비교 정렬

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 정렬 알고리즘의 종류
- 2.1. 대표적인 비교 정렬 알고리즘
3. 비교 정렬의 성능
- 3.1. 비교 정렬의 장점
- 3.2. 비교 정렬의 한계
4. 비비교 정렬
- 4.1. 대표적인 비비교 정렬 알고리즘
5. 비교 횟수의 하한
- 5.1. 정보 이론적 하한
- 5.2. 결정 트리 모델
6. 추가 설명
- 6.1. 이미 정렬된 리스트 정렬
  - 6.1.1. 적응형 힙 정렬
참조

1. 개요

비교 정렬은 요소 간의 비교를 통해 정렬을 수행하는 알고리즘을 의미한다. 퀵 정렬, 힙 정렬, 병합 정렬 등이 있으며, 평균적으로 O(n log n)의 시간 복잡도를 가진다. 비교 정렬은 다양한 데이터 유형에 적용 가능하고 정렬 방식을 세밀하게 제어할 수 있지만, 비비교 정렬에 비해 성능의 한계가 있다. 정렬된 정도에 따라 성능이 향상되는 적응형 정렬 기법도 존재한다.

더 읽어볼만한 페이지

정렬 알고리즘 - 합병 정렬
합병 정렬은 분할 정복 알고리즘을 사용하여 리스트를 재귀적으로 분할하고 정렬된 부분 리스트를 병합하는 비교 기반 정렬 알고리즘으로, O(n log n)의 시간 복잡도를 가지며 안정 정렬에 속하고 연결 리스트 정렬 및 외부 정렬에 유용하다.
정렬 알고리즘 - 퀵 정렬
퀵 정렬은 토니 호어가 개발한 분할 정복 방식의 효율적인 정렬 알고리즘으로, 피벗을 기준으로 리스트를 분할하여 정렬하는 과정을 재귀적으로 반복하며 다양한 최적화 기법과 변형이 존재한다.

비교 정렬
정렬 알고리즘
종류	비교 정렬 알고리즘
시간 복잡도 (최선)	O(n log n) (대부분의 효율적인 알고리즘)
시간 복잡도 (평균)	O(n log n) (대부분의 효율적인 알고리즘)
시간 복잡도 (최악)	O(n^2) (일부 비효율적인 알고리즘, 예를 들어 버블 정렬, 삽입 정렬, 선택 정렬)
공간 복잡도 (최악)	O(1) (제자리 정렬) 또는 O(n) (일부 알고리즘, 예를 들어 병합 정렬)
설명
개요	두 개의 요소를 비교하여 상대적인 순서를 결정하는 정렬 알고리즘의 한 종류이다.
작동 방식	요소 쌍을 비교하고 필요에 따라 교환하여 올바른 순서가 될 때까지 반복한다.
특징	다양한 종류의 데이터에 적용 가능 구현이 비교적 간단 대규모 데이터 세트에는 비효율적일 수 있음
예시 알고리즘
기본 알고리즘	버블 정렬 삽입 정렬 선택 정렬
효율적인 알고리즘	병합 정렬 힙 정렬 퀵 정렬
장단점
장점	구현이 간단하고 이해하기 쉬움
단점	대규모 데이터 세트에서 비효율적일 수 있음

2. 정렬 알고리즘의 종류

비교 정렬은 원소 간의 비교를 통해 정렬을 수행하는 알고리즘이다. 잘 알려진 비교 정렬 알고리즘은 다음과 같다.

퀵 정렬
힙 정렬
셸 정렬
합병 정렬
인트로소트
삽입 정렬
선택 정렬
거품 정렬
홀짝 정렬
칵테일 셰이커 정렬
순환 정렬
합병 삽입 정렬
부드러운 정렬
팀 정렬
블록 정렬

2. 1. 대표적인 비교 정렬 알고리즘

다음은 널리 사용되는 비교 정렬 알고리즘이다.

퀵 정렬
힙 정렬
셸 정렬
합병 정렬
인트로소트
삽입 정렬
선택 정렬
거품 정렬
홀짝 정렬
칵테일 정렬
순환 정렬
합병 삽입 정렬
부드러운 정렬
팀 정렬
블록 정렬

3. 비교 정렬의 성능

비교 정렬은 평균적인 경우 Ω(n log n) 비교 연산이 필요하며,^[2] 이는 선형 로그 시간으로 알려져 있다. 이는 비교만으로는 사용할 수 있는 정보가 제한적이기 때문이다. 합병 정렬, 힙 정렬, 인트로소트는 비교 횟수 측면에서 점근적으로 최적이지만, 다른 연산은 무시된다. 비비교 정렬은 비교 외의 연산을 사용하여 O(n) 성능을 달성할 수 있다.

적응형 정렬인 삽입 정렬과 같은 일부 정렬은 이미 정렬되었거나 거의 정렬된 목록에서 O(n) 시간에 실행된다. Ω(n log n) 하한은 입력 목록이 가능한 모든 순서일 수 있는 경우에만 적용된다.

실제 정렬 속도 측정에서는 알고리즘이 캐시된 컴퓨터 메모리를 최적으로 사용할 수 있는지, 정렬된 데이터가 사용자에게 빠르게 표시되는지 등의 이점을 고려해야 할 수 있다.

3. 1. 비교 정렬의 장점

비교 정렬은 비교 함수를 통해 다양한 데이터 유형을 정렬하고, 목록의 정렬 방식을 세밀하게 제어할 수 있다는 실질적인 이점을 제공한다.^[2] 예를 들어, 비교 함수의 결과를 반전하면 목록을 역순으로 정렬할 수 있으며, 각 부분을 순서대로 비교하는 비교 함수를 생성하기만 하면 튜플 목록을 사전식 순서로 정렬할 수 있다.

비교 정렬은 부동 소수점 숫자의 순서와 같은 복잡한 순서에도 쉽게 적용할 수 있다. 또한 비교 함수가 작성되면 수정 없이 모든 비교 정렬을 사용할 수 있다. 반면 비비교 정렬은 일반적으로 각 데이터 유형에 대해 특수한 버전이 필요하다.

이러한 유연성과 최신 컴퓨터에서 퀵 정렬, 힙 정렬, 합병 정렬 등 비교 정렬 알고리즘의 효율성 덕분에, 대부분의 실질적인 작업에서 비교 정렬이 널리 선호된다.^[2]

3. 2. 비교 정렬의 한계

비교 정렬은 평균적인 경우 Ω(''n'' log ''n'') 비교 연산의 하한을 가져야 하며,^[2] 이는 선형 로그 시간으로 알려져 있다. 이는 비교만으로는 사용할 수 있는 정보가 제한적이기 때문이며, 다르게 말하면 전순서 집합의 모호한 대수 구조 때문이다. 이러한 의미에서 합병 정렬, 힙 정렬, 인트로소트는 수행해야 하는 비교 횟수 측면에서 점근적으로 최적이지만, 이 지표는 다른 연산을 무시한다. 비비교 정렬은 비교 외의 연산을 사용하여 O(''n'') 성능을 달성할 수 있으므로 이 하한선을 회피할 수 있다(요소 크기가 일정하다고 가정).

비교 정렬은 일부 목록에서 더 빠르게 실행될 수 있다. 적응형 정렬인 삽입 정렬과 같은 많은 정렬은 이미 정렬되었거나 거의 정렬된 목록에서 O(''n'') 시간에 실행된다. Ω(''n'' log ''n'') 하한은 입력 목록이 가능한 모든 순서일 수 있는 경우에만 적용된다.

정렬 속도의 실제 측정에서는 일부 알고리즘이 상대적으로 빠른 캐시된 컴퓨터 메모리를 최적으로 사용할 수 있는 능력이나, 전체 목록이 정렬될 때까지 출력을 사용할 수 없는 정렬 방법과 달리 정렬된 데이터가 사용자에게 빠르게 표시되기 시작하는 정렬 방법(그런 다음 사용자의 읽기 속도가 제한 요소가 됨)의 이점을 고려해야 할 수 있다.

이러한 제약에도 불구하고 비교 정렬은 비교 함수에 대한 제어를 통해 다양한 데이터 유형을 정렬하고 목록의 정렬 방식을 세밀하게 제어할 수 있다는 실질적인 이점을 제공한다. 예를 들어, 비교 함수의 결과를 반전하면 목록을 역순으로 정렬할 수 있으며, 각 부분을 순서대로 비교하는 비교 함수를 생성하기만 하면 튜플 목록을 사전식 순서로 정렬할 수 있다.

비교 정렬은 일반적으로 부동 소수점 숫자의 순서와 같은 복잡한 순서에 더 쉽게 적응한다. 또한 비교 함수가 작성되면 수정 없이 모든 비교 정렬을 사용할 수 있다. 비비교 정렬은 일반적으로 각 데이터 유형에 대해 특수한 버전이 필요하다.

이러한 유연성과 최신 컴퓨터에서 위에서 언급한 비교 정렬 알고리즘의 효율성은 대부분의 실질적인 작업에서 비교 정렬을 널리 선호하게 만들었다.

4. 비비교 정렬

비교 정렬은 평균적인 경우 Ω(''n'' log ''n'') 비교 연산의 하한을 가져야 하며, 이는 선형 로그 시간으로 알려져 있다.^[2] 이는 비교만으로는 사용할 수 있는 정보가 제한적이기 때문이다. 비비교 정렬은 비교 외의 연산을 사용하여 O(''n'') 성능을 달성할 수 있으므로 이 하한선을 회피할 수 있다(요소 크기가 일정하다고 가정).^[2]

두 숫자의 합으로 쌍을 정렬하는 문제는 이러한 제한을 받지 않는다. 가장 잘 알려진 알고리즘은 여전히 O(''n''² log ''n'') 시간이 걸리지만, 비교 횟수는 O(''n''²)에 불과하다.

4. 1. 대표적인 비비교 정렬 알고리즘

계수 정렬은 키가 작은 정수인 경우(n에 비해) 선형 시간에 실행되는 알고리즘의 한 예시이다.^[1] 기수 정렬과 같은 다른 정수 정렬 알고리즘은 점근적으로 비교 정렬보다 빠르지는 않지만, 실제로는 더 빠를 수 있다.^[1]

5. 비교 횟수의 하한

비교 정렬 알고리즘은 정렬할 요소가 n개일 때, 최소 $\log_2(n!)$ 번의 비교가 필요하다. 이는 스털링 근사를 통해 $n \log n$ 으로 근사할 수 있으며, 이 경계는 점근적으로 빡빡하다.

고유한 숫자 목록이 주어졌을 때, 정렬된 목록은 $n$ 팩토리얼 순열 중 정확히 하나이다. 정렬 알고리즘은 비교를 통해 올바른 순열을 식별할 수 있을 만큼 충분한 정보를 얻어야 한다. 알고리즘이 최대 $f(n)$ 단계 후에 완료된다면, $2^{f(n)}$ 개 이상의 경우를 구별할 수 없으므로, $2^{f(n)}\geq n!$ 또는 $f(n)\geq\log_2(n!).$ 가 성립한다.

$\log_2(n!)$ 의 하한은 $n! = n (n-1) \cdots 1$ 의 처음 $n/2$ 개 요소를 고려하여 다음과 같이 구할 수 있다.

: $\log_2(n!) \geq \log_2\left(\left(\frac{n}{2}\right)^\frac{n}{2}\right) = \frac{n}{2} \frac{\log n}{\log 2} - \frac{n}{2} = \Theta(n \log n).$

: $\log_2(n!) = \Omega(n \log n).$

스털링 근사를 사용하면 더 정확한 경계를 얻을 수 있으며, 병합 정렬과 같이 최악의 경우 이 경계에 도달하는 알고리즘이 존재한다.

비교 횟수에 대한 ''절대적'' 하한은 $\left\lceil\log_2(n!)\right\rceil$ 이지만, 이 값은 정확하지 않은 경우도 있다. 예를 들어, $\left\lceil\log_2(13!)\right\rceil = 33$ 이지만, 13개 요소를 정렬하는 데 필요한 최소 비교 횟수는 34이다.^[5]^[6]^[7]

주어진 항목 수를 정렬하는 데 필요한 비교 횟수를 ''정확하게'' 결정하는 것은 작은 ''n''값에 대해서도 계산적으로 어려운 문제이며, 간단한 공식은 알려져 있지 않다. 다음 표는 n값에 따른 $\left\lceil\log_2(n!)\right\rceil$ 값과 최소 비교 횟수를 보여준다.

n	$\left\lceil\log_2(n!)\right\rceil$	최소 비교 횟수
1	0	0
2	1	1
3	3	3
4	5	5
5	7	7
6	10	10
7	13	13
8	16	16
9	19	19
10	22	22
11	26	26
12	29	30^[3]^[4]
13	33	34^[5]^[6]^[7]
14	37	38^[7]
15	41	42^[8]^[9]^[10]
16	45	46^[11]
17	49	50^[11]
18	53	54^[11]
19	57	58^[10]
20	62	62
21	66	66
22	70	71^[7]

5. 1. 정보 이론적 하한

모든 키가 고유하고, 입력이 모든 가능한 ''n''개 요소의 순열 집합에서 균일하게 선택된 임의 순열이라고 가정하면, 평균적으로

\log_2(n!)

번 미만의 비교로는 입력 순서를 결정할 수 없다.

이는 정보 이론을 통해 가장 쉽게 알 수 있다. 이러한 임의 순열의 섀넌 엔트로피는

\log_2(n!)

비트이다. 비교는 두 가지 결과만 제공할 수 있으므로, 제공하는 최대 정보량은 1비트이다. 따라서 ''k''번의 비교 후, 해당 비교 결과가 주어지면, 순열의 나머지 엔트로피는 평균적으로 최소

\log_2(n!) - k

비트이다. 정렬을 수행하려면 완전한 정보가 필요하므로, 나머지 엔트로피는 0이어야 한다. 따라서 ''k''는 평균적으로 최소

\log_2(n!)

여야 한다.

정보 이론을 통해 도출된 하한은 '정보 이론적 하한'으로 표현된다. 정보 이론적 하한은 정확하지만, 반드시 가장 강력한 하한은 아니다. 어떤 경우에는 문제의 정보 이론적 하한이 실제 하한과 거리가 멀 수도 있다. 예를 들어, 선택의 정보 이론적 하한은

\left\lceil\log_2(n)\right\rceil

이지만, 적대적 논증에 의해

n-1

번의 비교가 필요하다. 정보 이론적 하한과 실제 하한 사이의 상호 작용은 정수 함수를 하한하는 실수 함수와 매우 유사하다. 그러나 평균적인 경우를 고려할 때는 이것이 정확하지 않다.

평균적인 경우를 분석하는 동안 무슨 일이 일어나는지 밝히기 위해, 핵심은 '평균'이 무엇을 의미하는가 하는 것이다. 정보 이론에 대한 약간의 지식을 통해, 정보 이론적 하한은 전체 순열 집합에 대한 평균을 낸다. 그러나 모든 컴퓨터 알고리즘은 각 순열을 문제의 개별 인스턴스로 취급해야 한다. 따라서 우리가 찾고 있는 평균 하한은 모든 개별 사례에 대해 평균을 낸다.

컴퓨터의 달성 불가능성과 관련된 하한을 찾기 위해, 결정 트리 모델을 채택한다. 결정 트리 모델에서, 보여져야 할 하한은

n!

개의 리프(각 리프는 순열에 해당)를 가진 이진 트리의 루트에서 리프까지의 경로의 평균 길이의 하한이다. 주어진 수의 리프를 가진 이진 트리의 최소 평균 길이는 균형 잡힌 완전 이진 트리에 의해 달성된다. 왜냐하면 다른 이진 트리는 리프 쌍을 더 높은 위치로 이동하여 경로 길이를 줄일 수 있기 때문이다. 신중한 계산을 통해,

n!

개의 리프를 가진 균형 잡힌 완전 이진 트리의 경우, 루트에서 리프까지의 경로의 평균 길이는 다음과 같다.

:

\frac{(2n! - 2^{\lfloor \log_2 n! \rfloor + 1}) \cdot \lceil \log_2 n! \rceil + (2^{\lfloor \log_2 n! \rfloor + 1} - n!) \cdot \lfloor \log_2 n! \rfloor}{n!} = \lceil \log_2 n! \rceil + 1 - \frac{2^{\lceil \log_2 n! \rceil}}{n!}

예를 들어,

n = 3

의 경우, 평균적인 경우에 대한 정보 이론적 하한은 약 2.58이고, 결정 트리 모델을 통해 도출된 평균 하한은 8/3, 약 2.67이다.

여러 항목이 동일한 키를 가질 수 있는 경우, "평균적인 경우"라는 용어에 대한 명확한 통계적 해석이 없으므로, 키의 분포에 대한 특정 가정을 하지 않고서는 위와 같은 논증을 적용할 수 없다.

5. 2. 결정 트리 모델

결정 트리 모델을 사용하면 평균 비교 횟수의 하한을 도출할 수 있다. 키가 모두 고유하고, 입력이 가능한 모든 순열 집합에서 균일하게 선택된 임의 순열이라고 가정하면, 평균적으로

\log_2(n!)

번 미만의 비교로는 입력 순서를 결정할 수 없다.

이는 정보 이론의 개념을 통해 쉽게 확인할 수 있다. 임의 순열의 섀넌 엔트로피는

\log_2(n!)

비트이다. 비교는 두 가지 결과만 제공하므로 최대 정보량은 1비트이다. 따라서 ''k''번 비교 후 순열의 나머지 엔트로피는 평균적으로 최소

\log_2(n!) - k

비트이다. 정렬을 수행하려면 완전한 정보가 필요하므로 나머지 엔트로피는 0이어야 한다. 따라서 ''k''는 평균적으로 최소

\log_2(n!)

여야 한다.

정보 이론을 통해 도출된 하한은 '정보 이론적 하한'으로 표현된다. 정보 이론적 하한은 정확하지만 반드시 가장 강력한 하한은 아니다. 어떤 경우에는 문제의 정보 이론적 하한이 실제 하한과 거리가 멀 수 있다. 예를 들어, 선택의 정보 이론적 하한은

\left\lceil\log_2(n)\right\rceil

이지만, 적대적 논증에 의해

n-1

번의 비교가 필요하다.

평균적인 경우를 분석할 때, 정보 이론적 하한은 전체 순열 집합에 대한 평균을 낸다. 그러나 모든 컴퓨터 알고리즘은 각 순열을 문제의 개별 인스턴스로 취급해야 한다. 따라서 우리가 찾고 있는 평균 하한은 모든 개별 사례에 대해 평균을 내야 한다.

결정 트리 모델에서, 하한은

n!

개의 리프(각 리프는 순열에 해당)를 가진 이진 트리의 루트에서 리프까지의 경로의 평균 길이의 하한이다. 주어진 수의 리프를 가진 이진 트리의 최소 평균 길이는 균형 잡힌 완전 이진 트리에 의해 달성된다.

n!

개의 리프를 가진 균형 잡힌 완전 이진 트리의 경우, 루트에서 리프까지의 경로의 평균 길이는 다음과 같다.

:

\frac{(2n! - 2^{\lfloor \log_2 n! \rfloor + 1}) \cdot \lceil \log_2 n! \rceil + (2^{\lfloor \log_2 n! \rfloor + 1} - n!) \cdot \lfloor \log_2 n! \rfloor}{n!} = \lceil \log_2 n! \rceil + 1 - \frac{2^{\lceil \log_2 n! \rceil}}{n!}

예를 들어,

n = 3

의 경우, 평균적인 경우에 대한 정보 이론적 하한은 약 2.58이고, 결정 트리 모델을 통해 도출된 평균 하한은 8/3, 약 2.67이다.

여러 항목이 동일한 키를 가질 수 있는 경우, "평균적인 경우"라는 용어에 대한 명확한 통계적 해석이 없으므로, 키의 분포에 대한 특정 가정을 하지 않고서는 위와 같은 논증을 적용할 수 없다.

6. 추가 설명

다음은 잘 알려진 비교 정렬 알고리즘이다.

퀵 정렬
힙 정렬
셸 정렬
합병 정렬
인트로소트
삽입 정렬
선택 정렬
거품 정렬
홀짝 정렬
칵테일 정렬
순환 정렬
합병 삽입 정렬
부드러운 정렬
팀 정렬

6. 1. 이미 정렬된 리스트 정렬

적응 정렬은 목록이 이미 정렬에 가까울수록 정렬에 필요한 비교 횟수가 줄어드는 특징을 활용한다. 적응 힙 정렬이 그 예시 중 하나이다.^[12]

6. 1. 1. 적응형 힙 정렬

적응형 힙 정렬은 데카르트 트리를 기반으로 하는 정렬 알고리즘이다. 이 알고리즘은 주어진 수열에서 모든 값

x

에 대해,

x

아래에서

x

위로 또는 그 반대로 이동하는 횟수의 평균인

k

에 대해

O(n\log k)

시간이 걸린다.^[12]

참조

_[1] 학술지 The Art of Computer Programming, Volume 3, Sorting and Searching http://dx.doi.org/10[...] 1974-11-01
_[2] 서적 Introduction to Algorithms
_[3] 간행물 Applications of a language for computing in combinatorics 1966
_[4] 서적 Elements of Combinatorial Computing Pergamon Press 1971
_[5] 간행물 Thirty four comparisons are required to sort 13 items 1994
_[6] 간행물 Sorting 13 elements requires 34 comparisons 2002
_[7] 간행물 New results in minimum-comparison sorting 2004
_[8] 학위논문 Computer assisted research of posets University of Warsaw 2006
_[9] 학술지 The Ford-Johnson algorithm is still unbeaten for less than 47 elements
_[10] 학술지 最少比较排序问题中S（15）和S（19）的解决 http://fcst.ceaj.org[...] 2007-10
_[11] 간행물 Lower Bounds for Sorting 16, 17, and 18 Elements Society for Industrial and Applied Mathematics 2023
_[12] 서적 WADS '89: Proceedings of the Workshop on Algorithms and Data Structures Springer-Verlag
_[13] 서적 The art of computer programming, volume 3: (2nd ed.) sorting and searching https://dl.acm.org/d[...] Addison Wesley Longman Publishing Co., Inc. 1998

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com